package com.kavinz.algo.list;

import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * Doubly linked list , every node of which have two pointers pointing at the
 * previous node and next node respectively
 * 
 * @author Kevin Zhao
 * 
 */
public class DoublyLinkedList<E> implements List<E> {

	private Node first;// pointer to the first node
	private Node last;// pointer to the last node
	private int size;// the size of the list

	/**
	 * Internal node storing the element put into the list
	 * 
	 * @author Kevin Zhao
	 * 
	 * @param <E>
	 */
	class Node {
		Node pre;
		Node next;
		E item;
	}

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	public boolean contains(Object o) {
		// TODO Auto-generated method stub
		return false;
	}

	public Iterator<E> iterator() {
		// TODO Auto-generated method stub
		return null;
	}

	public Object[] toArray() {
		// TODO Auto-generated method stub
		return null;
	}

	public <T> T[] toArray(T[] a) {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * insert the given node to the tail of the list
	 */
	public boolean add(E e) {
		if (e == null)
			return false;
		// construct new node
		Node newNode = new Node();
		newNode.item = e;
		if (last == null && first == null)// this happens when the list is empty
		{
			// set the two pointers
			first = last = newNode;
		} else// when the list is not empty
		{
			// insert the new node after the node where the last-pointer is
			// pointing at
			newNode.pre = last;
			last.next = newNode;
			// update the last-pointer
			last = newNode;
		}
		// increments size of the list
		size++;
		// return
		return true;
	}

	public boolean remove(Object o) {
		return false;
	}

	public boolean containsAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean addAll(Collection<? extends E> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean addAll(int index, Collection<? extends E> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean removeAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public boolean retainAll(Collection<?> c) {
		// TODO Auto-generated method stub
		return false;
	}

	public void clear() {
		// TODO Auto-generated method stub

	}

	public E get(int index) {
		if (!isElementIndex(index))
			throw new IndexOutOfBoundsException("index out of bounds");
		// traverse the list and find the node at the specified index
		Node node = traverse(index);

		return node == null ? null : node.item;
	}

	public E set(int index, E element) {
		// TODO Auto-generated method stub
		return null;
	}

	public void add(int index, E element) {
		if (!isPositionIndex(index))
			throw new IndexOutOfBoundsException("index out of bounds");
		// construct the new node
		Node newNode = new Node();
		newNode.item = element;
		// traverse the list and find the node at the specified index
		Node node = traverse(index);
		// insert at the tail of the list
		if (node == null)
			add(element);
		else if (index == 0)// insert at the head of the list
		{
			// insertion
			newNode.next = first;
			first.pre = newNode;
			// update two pointers
			first = newNode;
			// increments the size
			size++;
		}
		// insert at the middle of the list
		else {
			// insert the new node at the position indicated by the index
			// link the node.pre with newNode
			node.pre.next = newNode;
			newNode.pre = node.pre;
			// link the newNode with node
			newNode.next = node;
			node.pre = newNode;
			// increments the size
			size++;
		}

	}

	public E remove(int index) {
		if (!isElementIndex(index))
			throw new IndexOutOfBoundsException("index out of bounds");
		E element = null;
		// 1.traverse the list and find the node at the specified index
		Node node = traverse(index);
		// 2.processing the special situation when there is only one node in the
		// list
		if (size == 1) {
			// preserver the element
			element = first.item;
			// deletion
			first = null;
			last = null;
			// decrements the size
			size--;
			return element;
		}
		// 3.1 deletion at the tail of the list
		if (index == size - 1) {
			// preserver the element
			element = last.item;
			// deletion
			last = last.pre;
			last.next = null;

		}
		// 3.2 deletion at the head of the list
		else if (index == 0) {
			// preserver the element
			element = first.item;
			// deletion
			first = first.next;
			first.pre = null;
		}
		// 3.3 deletion at the middle of the list
		else {
			// preserver the element
			element = node.item;
			// delete the node at the position indicated by the index
			// unlink the node.pre and newNode
			node.pre.next = node.next;
			node.next.pre = node.pre;
			// remove the node( Let gc do its work)
			node = null;
		}

		// 4.decrements the size
		size--;
		return element;
	}

	public int indexOf(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}

	public int lastIndexOf(Object o) {
		// TODO Auto-generated method stub
		return 0;
	}

	public ListIterator<E> listIterator() {
		// TODO Auto-generated method stub
		return null;
	}

	public ListIterator<E> listIterator(int index) {
		// TODO Auto-generated method stub
		return null;
	}

	public List<E> subList(int fromIndex, int toIndex) {
		// TODO Auto-generated method stub
		return null;
	}

	/**
	 * Tells if the argument is the index of a valid position for an iterator or
	 * an add operation.
	 */
	private boolean isPositionIndex(int index) {
		return index >= 0 && index <= size;
	}

	/**
	 * Tells if the argument is the index of an existing element.
	 */
	private boolean isElementIndex(int index) {
		return index >= 0 && index < size;
	}

	/**
	 * return the node at the specified index of the list
	 * 
	 * @param index
	 * @return
	 */
	private Node traverse(int index) {
		if (index >= size)
			return null;
		if (index == 0)
			return first;
		Node node = first;
		for (int i = 0; i < index; i++) {
			node = node.next;
		}
		return node;
	}

	public static void main(String[] args) {
		DoublyLinkedList<String> list = new DoublyLinkedList<String>();

		list.add("abcd");
		list.add("bbdd");
		list.add(2, "ccde");
		list.add(0, "ffas");
		list.add("zzz");
		list.add("34fasd");
		list.add("323");
		list.add("3agawasd");

		list.remove(0);
		list.remove(1);
		list.remove(list.size - 1);

		/** Test for other *******/
		for (int i = 0; i < list.size; i++) {
			System.out.println(list.get(i).toString());
		}
	}
}
